package com.example.sorts12.sorts;

/**
 * 快速排序实现
 * O(n) 时间复杂度内求无序数组中的第 K 大元素
 * 不能有重复元素
 * @auther lijiewei
 * @date 2021/8/26 11:10
 */
public class KthSmallest {

    /**
     * 求第 k 为元素（从小到大排序）
     * @param arr 数组
     * @param k 下标
     * @return
     * @author lijiewei
     * @date   2021/8/26 13:46
     */
    public static int kthSmallest(int[] arr, int k){
        if (null == arr || arr.length < k) {
            return -1;
        }
        int pivotIndex = parttion(arr, 0, arr.length - 1);
        while (pivotIndex + 1 != k) {
            if (pivotIndex + 1 < k) {
                pivotIndex = parttion(arr, pivotIndex + 1, arr.length - 1);
            } else {
                pivotIndex = parttion(arr, 0, pivotIndex - 1);
            }
        }
        return arr[pivotIndex];
    }

    /**
     * 分区排序，获取分区点位置
     * @param arr 数组
     * @param p 开始下标
     * @param r 结束下标
     * @return
     * @author lijiewei
     * @date   2021/8/26 11:22
     */
    private static int parttion(int[] arr, int p, int r) {
        //分区点
        int pivot = arr[r];

        //左边为小于区间，右边为大于区间, i为右边的第一位
        int i = p;
        for (int j = p; j < r; j++) {
            if(arr[j] < pivot) {
                swap(arr, i, j);
                i++;
            }
        }
        //将分区点和 i 位置交换
        swap(arr, i, r);
        return i;
    }

    /**
     * 交换数组arr中下标 i 和 j 的元素
     * @param arr 数组
     * @param i 下标
     * @param j 下标
     * @return
     * @author lijiewei
     * @date   2021/8/26 13:37
     */
    private static void swap(int[] arr, int i, int j) {
        if (i == j) {
            return;
        }

        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
